package com.leecode.xiehf.page_01;

/**
 * 给你一个字符串 s，找到 s 中最长的回文子串。
 * https://leetcode-cn.com/problems/longest-palindromic-substring/
 */
public class Solution_0005 {


    public static void main(String[] args) {
        Solution_0005 solution_0005 = new Solution_0005();
        String s = solution_0005.longestPalindrome("cbbd");
        System.out.println(s);
    }

    /**
     * 两种情况
     * 一种是aba
     * 一种是aa
     *
     * @param s
     * @return
     */
    public String longestPalindrome(String s) {
        int length = s.length();
        if (length < 2) {
            return s;
        }
        int max = 1;
        int begin = 0;
        // 后面不足的部分 没必要继续循环
        for (int i = 0; i < length - max / 2; i++) {
            int jishu = getPalindrome(s, length, i, i);
            int oushu = getPalindrome(s, length, i, i + 1);
            int curMax = Math.max(jishu, oushu);
            if (curMax > max) {
                max = curMax;
                begin = i - (max - 1) / 2;
            }
        }
        return s.substring(begin, begin + max);
    }

    private int getPalindrome(String s, int length, int left, int right) {
        int i = left;
        int j = right;
        while (i >= 0 && j < length && s.charAt(i) == s.charAt(j)) {
            i--;
            j++;
        }
        return j - i - 1;
    }
}
